package com.gitee.alg.sort

/**
 * Project Name: alg
 * Des:迭代版归并排序，  从下到上  迭代实现  =》 步长起始为1  即每个元素为一组 （有序），然后合并 步长加倍，再重复直到一次合并就包含整个数组
 * Package:com.gitee.alg.sort
 * 排序速度比不上归并属于用时间换空间， 问题是不稳定，（值相同的元素的顺序没有保障）
 *
 * @author Arlo Sun
 * @date 2021/4/26 - 22:41
 */
class IterateMergeSort<T : Comparable<T>>(override val compare: (T, T) -> Boolean) : ArraySort<T> {

    override fun sort(array: Array<T>, ascend: Boolean): Array<T> {

        val size = array.size

        // 作为镜像使用
        val clone = array.copyOf()
        var mirror = false
        var source = array
        var target = clone

        // i 即为 步长(当前子数组长度)

        //var i = size shr 1   因为这个  闹了个把小时  在下面看来看去楞是找不到哪里有问题。。。
        // 果然 看不出问题的代码就没问题 问题在没看到的地方

        //  i = 1, 2,4,8...
        var i = 1
        while (i < size) {

            for (j in source.indices step 2 * i) {
                var li = j
                var ri = j + i
                var ci = j

                //  按步长分成两两一组， 每组均是有序的，合并到镜像数组（右边可能是空的，左边也可能不满 e.g.  size = 5， i = 4 的时候）
                while (li < j + i && ri < j + 2 * i && ri < size) {
                    if (compare(source[li], source[ri])) target[ci++] = source[ri++] else target[ci++] = source[li++]
                }

                //下面处理 某段 不对称的部分
                while (ri < j + 2 * i && ri < size) {
                    target[ci++] = source[ri++]
                }

                while (li < j + i && li < size) {
                    target[ci++] = source[li++]
                }
            }

            //  避免循环数组拷贝
            mirror = !mirror
            if (mirror) {
                source = clone
                target = array
            } else {
                source = array
                target = clone
            }
            i *= 2
        }

        return if (mirror) clone else array
    }


}
